﻿/*
 * Copyright (c) 2013 European Bioinformatics Institute (EMBL-EBI)
 *                    John May <jwmay@users.sf.net>
 *
 * Contact: cdk-devel@lists.sourceforge.net
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at
 * your option) any later version. All we ask is that proper credit is given
 * for our work, which includes - but is not limited to - adding the above
 * copyright notice to the beginning of your source code files, and to any
 * copyright notice that you may distribute with programs based on this work.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * Any WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 U
 */

using static NCDK.Common.Base.Preconditions;

namespace NCDK.Graphs
{
    /// <summary>
    /// Compute the minimum cycle basis (MCB) of a graph. A cycle basis is a set of
    /// cycles that can be combined to generate all the cycles of a graph. The MCB is
    /// the basis of minimum weight (.Length). As an example, there are three cycles
    /// in <see href="http://en.wikipedia.org/wiki/Naphthalene"><i>naphthalene</i></see>.
    /// To generate the three cycles (cycle space) we actually only need two of the
    /// three cycles. The third cycle can be generated by combining the other two.
    /// Each combination of the two cycles is called a cycle basis. There is one
    /// basis with the two rings of size six and two bases with either ring of size
    /// six and the perimeter ring of size 10. The weights of each basis are 12
    /// (6+6), 16 (6+10), 16 (6+10). The basis of the two six member rings has
    /// minimum weight (12) and is thus the MCB of <i>naphthalene</i>.
    /// </summary>
    /// <remarks>
    /// The Smallest Set of Smallest Rings (SSSR) is normally used interchangeably
    /// with MCB although traditionally their meaning was different <token>cdk-cite-Berger04</token>
    /// Although the MCB can be used to generate all other cycles of a
    /// graph it may not be unique. A compound with a bridged ring system, such as 
    /// <see href="http://www.ebi.ac.uk/chebi/searchId.do?chebiId=CHEBI:115239"><i>3-quinuclidinol</i></see>, 
    /// has three equally valid minimum cycle bases. From
    /// any two six member rings the third ring can be generated by ⊕-sum
    /// (xor-ing) their edges. As there may be more than one MCB it should not be used
    /// as a <i>unique</i> descriptor. The smallest (but potentially exponential)
    /// <i>unique</i> set of short cycles which generates the cycle space is the
    /// union of all minimum cycle bases. This set is known as the <see cref="RelevantCycles"/>.
    /// The intersect of all minimum cycle bases (<see cref="EssentialCycles"/>) 
    /// is also unique. Although the number of <see cref="EssentialCycles"/>
    /// is polynomial it can not always be used to generate the cycle space.
    /// <see href="http://en.wikipedia.org/wiki/Cycle_space">Cycle Basis</see>
    /// </remarks>
    /// <seealso cref="RelevantCycles"/>
    // @author John May
    // @cdk.module core
    // @cdk.keyword sssr
    // @cdk.keyword smallest set of smallest rings
    // @cdk.keyword mcb
    // @cdk.keyword minimum cycle basis
    // @cdk.keyword cycle
    // @cdk.keyword ring
    // @cdk.keyword ring perception
    public sealed class MinimumCycleBasis
    {
        /// <summary>The minimum cycle basis.</summary>
        private readonly GreedyBasis basis;

        /// <summary>The graph used to form the basis.</summary>
        internal readonly int[][] graph;

        /// <summary>
        /// Generate the minimum cycle basis for a graph.
        /// </summary>
        /// <param name="graph">undirected adjacency list</param>
        /// <seealso cref="RingSearches.RingSearch.Fused"/>
        /// <seealso cref="GraphUtil.Subgraph(int[][], int[])"/>
        public MinimumCycleBasis(int[][] graph)
            : this(new InitialCycles(CheckNotNull(graph, nameof(graph), "No graph provided")))
        { }

        /// <summary>
        /// Generate the minimum cycle basis from a precomputed set of initial cycles.
        /// </summary>
        /// <param name="initial">set of initial cycles.</param>
        /// <exception cref="System.ArgumentNullException">null InitialCycles provided</exception>
        internal MinimumCycleBasis(InitialCycles initial)
            : this(initial, false)
        { }

        /// <summary>
        /// Generate the minimum cycle basis from a precomputed set of initial
        /// cycles. This constructor allows on to specify that the graph is
        /// connected which allows an optimisation to be used.
        /// </summary>
        /// <param name="initial">set of initial cycles.</param>
        /// <param name="connected">the graph is known to be connected</param>
        /// <exception cref="System.ArgumentNullException">null InitialCycles provided</exception>
        internal MinimumCycleBasis(InitialCycles initial, bool connected)
        {
            CheckNotNull(initial, nameof(initial), "No InitialCycles provided");

            this.graph = initial.Graph;
            this.basis = new GreedyBasis(initial.GetNumberOfCycles(), initial.GetNumberOfEdges());

            // a undirected unweighted connected graph there are |E| - (|V| + 1)
            // cycles in the minimum basis
            int lim = connected ? initial.GetNumberOfEdges() - graph.Length + 1 : int.MaxValue;

            // processing by size add cycles which are independent of smaller cycles
            foreach (var cycle in initial.GetCycles())
            {
                if (basis.Count < lim && basis.IsIndependent(cycle)) basis.Add(cycle);
            }
        }

        /// <summary>
        /// The paths of all cycles in the minimum cycle basis.
        /// </summary>
        /// <returns>array of vertex paths</returns>
        public int[][] GetPaths()
        {
            int[][] paths = new int[Count][];
            int i = 0;
            foreach (var c in basis.Members)
                paths[i++] = c.Path;
            return paths;
        }

        /// <summary>
        /// The number of the cycles in the minimum cycle basis.
        /// </summary>
        /// <returns>size of minimum cycle set</returns>
        public int Count => basis.Count;
    }
}
